package com.javabasic.algorithm.leetcode;

import java.util.HashMap;
import java.util.Map;
import java.util.Set;

/**
 * @author mir.xiong
 * @version 1.0
 * @description 简单题
 * @see [383. Ransom Note](https://leetcode-cn.com/problems/ransom-note/)
 * @since Created by work on 2021/12/4 5:06 下午
 */
public class RansomNote {

    /**
     * Map+暴力循环
     * @param ransomNote
     * @param magazine
     * @return
     */
    public boolean canConstruct(String ransomNote, String magazine) {
        int ransomNoteLen = ransomNote.length();
        Map<Integer, Integer> charToNums = new HashMap<>(ransomNoteLen);
        int orDefault, key;
        for (int i = 0; i < ransomNoteLen; i++) {
            key = ransomNote.charAt(i) - 'a';
            orDefault = charToNums.getOrDefault(key, 0);
            orDefault++;
            charToNums.put(key,orDefault);
        }
        int magazineLen = magazine.length(), num;
        for (int i = 0; i < magazineLen; i++) {
            key = magazine.charAt(i) - 'a';
            if (charToNums.containsKey(key)) {
                num = charToNums.get(key) - 1;
                charToNums.put(key,num);
            }
        }
        Set<Integer> keys = charToNums.keySet();
        for (Integer keyValue : keys) {
            if (charToNums.get(keyValue) > 0) {
                return false;
            }
        }
        return true;
    }



    /**
     * 数组(只有26个字母)+暴力循环
     * @param ransomNote
     * @param magazine
     * @return
     */
    public boolean canConstruct2(String ransomNote, String magazine) {
        int ransomNoteLen = ransomNote.length();
        final int CHAR_SIZE = 26;
        int[] chars = new int[CHAR_SIZE];
        int key;
        for (int i = 0; i < ransomNoteLen; i++) {
            key = ransomNote.charAt(i) - 'a';
            chars[key]++;
        }
        int magazineLen = magazine.length(), num;
        for (int i = 0; i < magazineLen; i++) {
            key = magazine.charAt(i) - 'a';
            chars[key]--;
        }
        for (int i = 0; i < CHAR_SIZE; i++) {
            if (chars[i] > 0) {
                return false;
            }
        }
        return true;
    }
}
